// 注：这里钻了一个空子，因为JavaScript/TypeScript中的是HashMap是默认与插入顺序相关的
// 所以基于Map底层的实现不需要用到链表

// LRU有序缓存类
export class LRUOrderdCache<T = number, U = number> {
    private cache: Map<T, U>;
    private size: number;
    constructor(capacity: number) {
        this.cache = new Map<T, U>();
        this.size = capacity;
    }
    // 取缓存方法
    get(key: T): U | -1 {
        const cache = this.cache;
        const value = cache.get(key);
        // 没找到key就直接返回-1
        if (cache.has(key) == false || value == undefined) return -1;
        // 存在cache的情况下记得调整hashMap的顺序，通过移除再插入实现
        cache.delete(key);
        cache.set(key, value);
        return value;
    }
    // 重置缓存方法
    put(key: T, value: U): void {
        const cache = this.cache;
        if (cache.has(key)) cache.delete(key);// 边缘情况，新加入的key存在重复需要先删除现存key
        // 判断是否超出缓存限制
        if (cache.size < this.size) {
            cache.set(key, value);
        } else {
            // 删除第一个key
            const firtsKey = cache.keys().next().value;
            cache.delete(firtsKey);
            // 加入新key
            cache.set(key, value);
        }
    }
}
